#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
#include<stack>
using namespace std;
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
    
};
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root)
    {
        if (root == nullptr)
            return {};
        vector<int> v;
        TreeNode* cur = root;
        stack<TreeNode*> mystack;
        while (cur || !mystack.empty())
        {
            while (cur)
            {
                mystack.push(cur);
                v.push_back(cur->val);
                cur = cur->left;
            }
            TreeNode* tmp = mystack.top();
            cur = tmp->right;
            mystack.pop();

        }
        return v;
    }
};
int main()
{
    TreeNode* n1 = new TreeNode(1);
    TreeNode* n2 = new TreeNode(2);
    TreeNode* n3 = new TreeNode(3);
    //n1->right = n2;
    n2->left = n3;
    TreeNode* n4 = nullptr;
    Solution().preorderTraversal(n1);

	return 0;
}